1. Field of the Invention
The present invention relates to redundant array of independent disks (RAID) systems for computing data parities by means of Galois field computation and also to Galois field product computation methods. More particularly, the invention relates to a RAID system and a Galois field product computation method suitable for recovering data from dual-disk failures.
2. Description of the Related Art
One approach to recovering data from dual-disk failures is RAID-6. In this RAID-6 scheme, a linear redundancy technique has been proposed, as disclosed in, for example, Japanese Unexamined Patent Application Publication No. 2000-259359 (FIGS. 5 and 6).
This technique is described below in the context of the configuration of the RAID-6 system shown in FIG. 14. Three data disk units (hard disk drives) 101, 102, and 103 and two parity disk units (hard disk drives), i.e., first and second disk units 104 and 105, are connected to a RAID controller 110.
In the linear redundancy technique, two parities are generated from data. The first parity P is generated, as shown in FIG. 15, as a result of adding data items D1, D2, and D3, i.e., calculating exclusive OR (XOR), as in the known RAID-5 scheme. The first parity P is stored in the first parity disk unit 104. The sign “+” shown in FIG. 15 represents XOR.
The second parity Q is generated by weighting the data items D1, D2, and D3 by means of Galois field product computation and by computing XOR of the resulting values. The second parity Q is stored in the second parity disk unit 105.
One Galois field generator is assigned to each of the data disk units 101, 102, and 103. In order to recover data from dual-disk failures, it is necessary that the Galois field generators assigned to the data disk units 101, 102, and 103 be different from each other. For example, if the number of data bits is 16, as shown in FIG. 15, 216 finite elements are provided as the Galois field GF(216). Additionally, four arithmetic operations can be performed on the Galois field according to a predetermined rule. The linear redundancy technique allows distribution of parities and is effective for detecting the occurrence of dual-disk failures and recovering data from such failures.
In generating parities utilizing a Galois field, as shown in FIG. 15, two variables, such as data and Galois field, are necessary for executing Galois field product computation. Accordingly, a longer processing time is required for generating parities than that for XOR computation of the RAID-5 scheme, i.e., computation of the ordinary parity P. Accordingly, the performance is reduced.
To simplify Galois field product computation, algorithms for weighting (product computation) a plurality of pieces of data by a factor α by means of shift, AND, XOR operations have been proposed, as disclosed in, for example, “The mathematics of RAID-6” by H. Peter Anvin, online paper, http://kernel.org/pub/linux/kernel/people/hpa/raid-6.pdf, accessed on Oct. 26, 2006). In this paper, expressions for generating parities and for recovering data when 8-bit data is used are disclosed from page 4 to page 5, and algorithms for weighting (product computation) by a factor α are described in the C language from the bottom column of page 6 to page 7.
The algorithms described in the C language are discussed below with reference to FIGS. 16 and 17 in the context of four symbol data, each symbol being represented by 8 bits. In FIG. 16, v represents subject data (32 bits) having four 8-bit symbols.
In step S100, the subject data v having four 8-bit symbols stored in a disk unit is loaded into a 32-bit register. Then, in step S101, the entire subject data v is shifted to the left (i.e., to a higher order) by one bit. The value of the resulting data v<<1 is as twice as large as that of the subject data v in units of 32 bits.
Then, in step S102, the bits of the shifted data v<<1 that have influenced other symbols by shifting the data v are masked. By the use of the mask value 0xfefefefe, the logical AND of the shifted data v<<1 and the mask value is computed so that the masked data vv is obtained. By this operation, the values of the rightmost bits (i.e., bits influenced by shifting the data v) of the four symbols are set to be 0. That is, an influence on the rightmost bit of a subject symbol by the most significant bit (MSB) of the right-adjacent symbol, which is caused by shifting all the 32 bits, can be prevented.
Subsequently, in step S103, the mask (v) function is generated, as shown in FIG. 17, from the subject data v. The MASK (v) function is generated such that, if the leftmost bit of an 8-bit symbol is 1, 8 bits “1.1111111” are set in that symbol, and if the leftmost bit of an 8-bit symbol is 0, 8 bits “00000000” are set in that symbol. That is, the mask (v) function is generated such that 8 bits of 1's are set for a symbol in which a carry is generated by shifting the subject data v and such that 8 bits of 0's are set for a symbol in which a carry is not generated by shifting the subject data v.
Details of the generation of the mask (v) function are given by the flowchart in FIG. 17. In step S110, logical AND of the subject data v and the mask value “0x80808080” in which 1 appears at 8 bit intervals and 0's are set in the other bit positions is computed. This mask value extracts the MSB of each symbol.
Then, in step S112, the logical AND value is shifted to the left by one bit, resulting in 32-bit data v<<1 (doubled data), and also, the logical AND value is shifted to the right by 7 bits, resulting in 32-bit data v>>7 ( 1/128 data). Then, the 32-bit data v>>7 is subtracted from the 32-bit data v<<1, resulting in the mask (v) function MASK(v). This function serves to distinguish symbols whose MSBs are 1 from symbols whose MSBs are not 1.
In step S104 in FIG. 16, logical AND of the coefficient value “0x1d1d1d1d” corresponding to a polynomial (=x8+x2+1) for generating an 8-bit Galois field GF(28) and the mask (v) function MASK(v) is computed. That is, among the four symbols, only the symbols whose MSBs are 1 are substituted by “00011101” of the coefficient value “0x1d1d1d1d”.
In step S105, XOR of the logical AND result and the masked subject data vv computed in step S102 is computed, resulting in the subject data v multiplied by a factor α, i.e., α·v. By repeating those steps once again, data α2·v can be obtained. Similarly, data αn·v can be obtained, where n is the number of times for which the above-described steps are repeated.
In the above-described related art, nine steps, i.e., a substitution step in step S100, a shift step in step S101, an AND step in step S102, an AND step, two shift steps, and one subtraction step in step S103 (FIG. 17), one AND step in step S104, and an XOR step in step S105, are required for implementing parallel processing for Galois field product computation on several symbols (four symbols in the example of the related art).